package 数组;
import java.util.*;
/**
 * 三数之和
 * 给定一个整数数组，找出所有满足条件的三元组，使得三元组中的三个数之和为0
 * 时间复杂度：O(n^2)，其中n为数组长度
 * 空间复杂度：O(1)
 */
public class threeSum {
    /**
     * 查找所有和为0的三元组
     * 使用双指针法，先对数组排序，然后固定一个数，使用左右指针寻找另外两个数
     * 
     * @param nums 输入的整数数组
     * @return 所有满足条件的三元组列表
     */
    public List<List<Integer>> thrSum(int[] nums){
        // Arrays.sort(nums); // 使用Java内置的排序方法
        quickSort(nums, 0, nums.length - 1); // 使用快速排序对数组进行排序
        List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表
        for(int i = 0; i < nums.length; i++){ // 遍历数组，固定第一个数
            if(nums[i] > 0) break; // 如果第一个数大于0，由于数组已排序，后面不可能有和为0的三元组
            if(i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的第一个数
            int j = i + 1, k = nums.length - 1; // 初始化左右指针
            while(j < k){ // 当左右指针相遇时结束
                int sum = nums[i] + nums[j] + nums[k]; // 计算当前三元组的和
                if(sum == 0){ // 找到和为0的三元组
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k]))); // 将三元组加入结果列表
                    while(j < k && nums[j] == nums[j + 1]) j++; // 跳过重复的第二个数
                    j++; // 移动左指针
                    while(j < k && nums[k] == nums[k - 1]) k--; // 跳过重复的第三个数
                    k--; // 移动右指针
                }else if(sum > 0){ // 如果和大于0，需要减小和
                    k--; // 移动右指针，使和变小
                }else if(sum < 0){ // 如果和小于0，需要增大和
                    j++; // 移动左指针，使和变大
                }
            }
        }
        return res; // 返回所有满足条件的三元组
    }

    /**
     * 快速排序算法
     * 对数组进行原地排序
     * 
     * @param nums 待排序的数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right){
        if(left >= right) return; // 如果左边界大于等于右边界，则返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 对左半部分进行快速排序
        quickSort(nums, pivot + 1, right); // 对右半部分进行快速排序
    }

    /**
     * 快速排序的分区操作
     * 将数组分为两部分，左边部分小于基准值，右边部分大于基准值
     * 
     * @param nums 待分区的数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的最终位置
     */
    private int partition(int[] nums, int left, int right){
        int val = nums[left]; // 选择左边界元素作为基准值
        while(left < right){ // 当左右指针相遇时结束
            while(nums[right] >= val && left < right) right--; // 从右向左找到第一个小于基准值的元素
            nums[left] = nums[right]; // 将找到的元素放到左边界
            while(nums[left] <= val && left < right) left++; // 从左向右找到第一个大于基准值的元素
            nums[right] = nums[left]; // 将找到的元素放到右边界
        }
        nums[left] = val; // 将基准值放到最终位置
        return left; // 返回基准值的最终位置
    }

    /**
     * 主函数
     * 处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示输入数组
     * 输出格式：所有和为0的三元组列表
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[s.length]; // 创建输入数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        threeSum ts = new threeSum(); // 创建实例
        System.out.println(ts.thrSum(nums)); // 输出所有和为0的三元组
        sc.close(); // 关闭输入流
    }
}
